{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Make Array Non-decreasing or Non-increasing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: convertArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组变为有序的最小操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 。在一步操作中，你可以：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>在范围&nbsp;<code>0 &lt;= i &lt; nums.length</code> 内选出一个下标 <code>i</code></li>\n",
    "\t<li>将 <code>nums[i]</code> 的值变为 <code>nums[i] + 1</code> <strong>或</strong> <code>nums[i] - 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回将数组 <code>nums</code> 变为 <strong>非递增</strong> 或<strong> 非递减 </strong>所需的 <strong>最小</strong> 操作次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,4,5,0]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "一种可行的操作顺序，能够将 nums 变为非递增排列：\n",
    "- nums[1] 加 1 一次，使其变为 3 。\n",
    "- nums[2] 减 1 一次，使其变为 3 。\n",
    "- nums[3] 减 1 两次，使其变为 3 。\n",
    "经过 4 次操作后，nums 变为 [3,3,3,3,0] ，按非递增顺序排列。\n",
    "注意，也可以用 4 步操作将 nums 变为 [4,4,4,4,0] ，同样满足题目要求。\n",
    "可以证明最少需要 4 步操作才能将数组变为非递增或非递减排列。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,3,4]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>数组已经是按非递减顺序排列了，无需执行任何操作，返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>数组已经是按非递减顺序排列了，无需执行任何操作，返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以设计并实现时间复杂度为 <code>O(n*log(n))</code> 的解法吗?</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [make-array-non-decreasing-or-non-increasing](https://leetcode.cn/problems/make-array-non-decreasing-or-non-increasing/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [make-array-non-decreasing-or-non-increasing](https://leetcode.cn/problems/make-array-non-decreasing-or-non-increasing/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,4,5,0]', '[2,2,3,4]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heapreplace\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def cao(y):\n",
    "            h = []\n",
    "            cost = 0\n",
    "            for v in y:\n",
    "                if h and v < -h[0]:\n",
    "                    cost += -v - h[0]\n",
    "                    heapreplace(h, -v)\n",
    "                heappush(h, -v)\n",
    "            return cost\n",
    "\n",
    "        t = cao(nums)\n",
    "        x = nums[::-1]\n",
    "        x = cao(x)\n",
    "        return min(t, x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        \n",
    "        def cao(y):\n",
    "            h=[]\n",
    "            cost=0\n",
    "            for v in y:\n",
    "                if h  and v< -h[0]:\n",
    "                    cost += -v -h[0] \n",
    "                    heapreplace(h,-v)\n",
    "                heappush(h,-v)\n",
    "            return cost\n",
    "                    \n",
    "        t=cao(nums)\n",
    "        x=nums[::-1]\n",
    "        x=cao(x)\n",
    "        return t if t<x else x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "\n",
    "        def cao(y):\n",
    "            h=[]\n",
    "            cost=0\n",
    "            for v in y:\n",
    "                if h  and v< -h[0]:\n",
    "                    cost += -v -h[0] \n",
    "                    heapreplace(h,-v)\n",
    "                heappush(h,-v)\n",
    "            return cost\n",
    "                    \n",
    "        t=cao(nums)\n",
    "        x=nums[::-1]\n",
    "        x=cao(x)\n",
    "        return t if t<x else x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ceil = 1001\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        increase = [0]*ceil\n",
    "        for num in nums:\n",
    "            increase[0] += abs(num)\n",
    "            for j in range(1, ceil):\n",
    "                increase[j] = min(increase[j-1], increase[j]+abs(num-j))\n",
    "\n",
    "        decrease = [0]*ceil\n",
    "        for i in range(n-1, -1, -1):\n",
    "            num = nums[i]\n",
    "            decrease[0] += abs(num)\n",
    "            for j in range(1, ceil):\n",
    "                decrease[j] = min(decrease[j-1], decrease[j]+abs(num-j))\n",
    "        return min(decrease[-1], increase[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\"\"\"\n",
    "            res, pq = 0, []  # 大根堆\n",
    "            for num in nums:\n",
    "                if not pq:\n",
    "                    heappush(pq, -num)\n",
    "                else:\n",
    "                    preMax = -pq[0]\n",
    "                    if preMax > num:\n",
    "                        res += preMax - num\n",
    "                        heappushpop(pq, -num)\n",
    "                    heappush(pq, -num)\n",
    "            return res\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def convertArray(self, a: List[int]) -> int:\n",
    "        def f(x):\n",
    "            a = x \n",
    "            ans = 0\n",
    "            b = SortedList([a[0]])\n",
    "            for j in a[1:]:\n",
    "                if j<b[-1]:\n",
    "                    t = b.pop() \n",
    "                    ans += (t - j)\n",
    "                    b.add(j)\n",
    "                b.add(j)\n",
    "            return ans \n",
    "        return min(f(a), f(a[::-1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def cal(A):\n",
    "            pq = []\n",
    "            res = 0\n",
    "            for a in A:\n",
    "                heappush(pq,-a)\n",
    "                if -pq[0]>a:\n",
    "                    res += -pq[0]-a\n",
    "                    heappushpop(pq,-a)\n",
    "            return res\n",
    "        return min(cal(nums),cal(nums[::-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\"\"\"\n",
    "            res, pq = 0, []  # 大根堆\n",
    "            for num in nums:\n",
    "                if not pq:\n",
    "                    heappush(pq, -num)\n",
    "                else:\n",
    "                    preMax = -pq[0]\n",
    "                    if preMax > num:\n",
    "                        res += preMax - num\n",
    "                        heappushpop(pq, -num)\n",
    "                    heappush(pq, -num)\n",
    "            return res\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "        \n",
    "\n",
    "    def convertArray2(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\"\"\"\n",
    "            n, max_ = len(nums), max(nums)\n",
    "\n",
    "            dp = [[int(1e20)] * (max_ + 1) for _ in range(n)]  # dp[i][num] 表示 前i个元素最num结尾的最小的代价是多少\n",
    "            for j in range((max_ + 1)):\n",
    "                dp[0][j] = abs(nums[0] - j)\n",
    "            for i in range(1, n):\n",
    "                preMin = int(1e20)\n",
    "                for j in range((max_ + 1)):\n",
    "                    preMin = min(preMin, dp[i - 1][j])\n",
    "                    dp[i][j] = preMin + abs(nums[i] - j)\n",
    "\n",
    "            return min(dp[-1])\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "        \n",
    "    def convertArray3(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\n",
    "\n",
    "            取得最小的操作次数时，数组末尾元素必须等于原数组中的某个元素\n",
    "            dp[i][num]表示前i个元素以num结尾的最小的代价是多少 时间复杂度 O(n*max(num[i]))\n",
    "            \"\"\"\n",
    "            n = len(nums)\n",
    "            allNums = sorted(set(nums))\n",
    "            m = len(allNums)\n",
    "\n",
    "            dp = [[int(1e20)] * m for _ in range(n)]\n",
    "            for j in range((m)):\n",
    "                dp[0][j] = abs(nums[0] - allNums[j])\n",
    "            for i in range(1, n):\n",
    "                preMin = int(1e20)\n",
    "                for j in range(m):\n",
    "                    preMin = min(preMin, dp[i - 1][j])\n",
    "                    dp[i][j] = preMin + abs(nums[i] - allNums[j])\n",
    "\n",
    "            return min(dp[-1])\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "from sortedcontainers import SortedList\n",
    "sys.setrecursionlimit(999999)\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def get_ans(list1):\n",
    "            ans = 0\n",
    "            sd1 = SortedList()\n",
    "            for i in list1:\n",
    "                if len(sd1) == 0:\n",
    "                    sd1.add(i)\n",
    "                else:\n",
    "                    if sd1[-1] > i:\n",
    "                        xx = sd1.pop()\n",
    "                        sd1.add(i)\n",
    "                        ans += xx - i\n",
    "                    sd1.add(i)\n",
    "            return ans\n",
    "\n",
    "        ans1 = get_ans(nums)\n",
    "        ans2 = get_ans(nums[::-1])\n",
    "        return min(ans1, ans2)\n",
    "\n",
    "a = Solution()\n",
    "print(a.convertArray([3,2,4,5,0]))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\n",
    "\n",
    "            取得最小的操作次数时，数组末尾元素必须等于原数组中的某个元素\n",
    "            \"\"\"\n",
    "            n = len(nums)\n",
    "            allNums = sorted(set(nums))\n",
    "            m = len(allNums)\n",
    "\n",
    "            dp = [[int(1e20)] * m for _ in range(n)]\n",
    "            for j in range((m)):\n",
    "                dp[0][j] = abs(nums[0] - allNums[j])\n",
    "            for i in range(1, n):\n",
    "                preMin = int(1e20)\n",
    "                for j in range(m):\n",
    "                    preMin = min(preMin, dp[i - 1][j])\n",
    "                    dp[i][j] = preMin + abs(nums[i] - allNums[j])\n",
    "\n",
    "            return min(dp[-1])\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\n",
    "\n",
    "            取得最小的操作次数时，数组末尾元素必须等于原数组中的某个元素\n",
    "            \"\"\"\n",
    "            n = len(nums)\n",
    "            allNums = sorted(set(nums))\n",
    "            m = len(allNums)\n",
    "\n",
    "            dp = [[int(1e20)] * m for _ in range(n)]\n",
    "            for j in range((m)):\n",
    "                dp[0][j] = abs(nums[0] - allNums[j])\n",
    "            for i in range(1, n):\n",
    "                preMin = int(1e20)\n",
    "                for j in range(m):\n",
    "                    preMin = min(preMin, dp[i - 1][j])\n",
    "                    dp[i][j] = preMin + abs(nums[i] - allNums[j])\n",
    "\n",
    "            return min(dp[-1])\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\"\"\"\n",
    "            n, max_ = len(nums), max(nums)\n",
    "\n",
    "            dp = [[int(1e20)] * (max_ + 1) for _ in range(n)]  # dp[i][num] 表示 前i个元素最num结尾的最小的代价是多少\n",
    "            for j in range((max_ + 1)):\n",
    "                dp[0][j] = abs(nums[0] - j)\n",
    "            for i in range(1, n):\n",
    "                preMin = int(1e20)\n",
    "                for j in range((max_ + 1)):\n",
    "                    preMin = min(preMin, dp[i - 1][j])\n",
    "                    dp[i][j] = preMin + abs(nums[i] - j)\n",
    "\n",
    "            return min(dp[-1])\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
